class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        array = {i: False for i in range(1, n + 1)}
        self.cnt = 0
        self.path = []

        def dfs():
            flag = True
            for num, status in array.items():
                if status: continue
                self.path.append(num)
                flag = False
                array[num] = True
                if dfs():
                    return True
                array[num] = False
                self.path.pop()
            if flag:
                self.cnt += 1
                if self.cnt == k:
                    self.ans = self.path[:]
                    return True

        dfs()
        return self.ans

if __name__ == '__main__':
    s = Solution()
    r = s.getPermutation(n = 3, k = 3)
    print(r)